(1) Field of the Invention
The present invention relates to program converting apparatuses which convert source programs written in a high-level language such as C language into machine language programs, and particularly relates to program converting apparatuses which perform instruction scheduling suitable to processors having a parallel processing mechanism.
(2) Description of the Related Art
In an instruction set included in a processor, latency, which is the number of cycles required to execute one instruction, usually varies depending on the instruction. Thus, even with the same instruction sequence, waiting time before an initiation of instruction execution varies depending on the order of execution. As a result, the number of execution cycles in total can be different. Specifically, the number of execution cycles in total is smaller when longer waiting time of instructions having long latency is successfully concealed with execution of other instructions.
In view of the above described characteristics, compilers that generate executable codes for processors optimize the number of execution cycles in total by rearranging instructions in a range where constraint of dependencies among instructions is satisfied. This is called instruction scheduling, and the ability of instruction scheduling significantly affects the performance of generated executable codes.
However, deriving optimally arranged instructions is a problem of Non-deterministic Polynomial time (NP) hard, and other optimization functions also affect the performance of executable codes. Thus, heuristic algorithms are adopted for an instruction scheduling function, and an algorithm that leads to a better result varies depending on a situation.
On the other hand, conventionally, as described in Patent Reference 1 (Japanese Patent No. 3311381) for example, there is an instruction scheduling method of (i) determining how registers are being used, (ii) selecting, based on the determination, one of an instruction scheduling method that gives priority to a parallelism and an instruction scheduling method that reduces the number of simultaneously active registers, and (iii) executing instruction scheduling conforming to the selected instruction scheduling method.
Alternatively, as described in Patent Reference 2 (Japanese Unexamined Patent Application Publication No. 2001-159983) for example, there is an instruction scheduling method of (i) referring to information of common sub-expression eliminated through a common sub-expression elimination that is one of the optimization methods, (ii) selecting, based on the information of whether or not the common sub-expression has been eliminated, an instruction scheduling method and (iii) executing instruction scheduling conforming to the selected instruction scheduling method.